package com.LeetCode.BackTrace;

import org.junit.Test;

/**
 * 查找单词 / 路径
 */
public class FindPath {

    public boolean exist(char[][] board, String word) {
        this.word = word;
        this.n = board.length;
        this.m = board[0].length;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(dfs(word, board, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    String word;

    int n,m;

    boolean flag;


    public boolean dfs(String word, char[][] board,int i, int j, int cur){
        if(cur == word.length()){
            flag = true;
            return true;
        }

        if(i<0 || i>=n || j<0 || j>=m || board[i][j] >= 256 || board[i][j] != word.charAt(cur))
            return false;


        if(!flag){
            board[i][j] += 256;


            boolean result = dfs(word, board, i + 1, j , cur+1) ||
                    dfs(word, board, i - 1, j , cur+1) ||
                    dfs(word, board, i, j + 1 , cur+1) ||
                    dfs(word, board, i, j - 1, cur+1);

            board[i][j] -= 256;

            return result;
        }else{
            return true;
        }
    }


    @Test
    public void test(){
        char[][] matrix = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        System.out.println(exist(matrix,"ABCCED"));
        System.out.println(exist(matrix,"SEE"));
        System.out.println(exist(matrix,"ABCB"));
    }
}
